//
//  LowestCommonAncestor.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/7/16.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  236. 二叉树的最近公共祖先

import UIKit

/*
 236. 二叉树的最近公共祖先


 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]



  

 示例 1:

 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 输出: 3
 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
 示例 2:

 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 输出: 5
 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
  

 说明:

 所有节点的值都是唯一的。
 p、q 为不同节点且均存在于给定的二叉树中。
 */

/*
 官解思路:
 用x表示节点，f(x)表示以x为根的节点是否包含 p 和 q 两个节点。用lson和rson分别表示x的左右孩子
 则有为了满足题解可推出一下公示
    f(lson) && f(frson)   ||   [(x==p)||(x==q) && f(lson)||f(rson)]
 
 f(lson) && f(frson) 表示x的左右孩子必然分别不重复得包含了p和q，此时x就是他们的最近祖先。
 
 还有一种情况，x恰好就是p或q，且其左或者右孩子也包含了另外一个点
 
 */

class LowestCommonAncestor: NSObject {
    
    /*
     递归法
     （1） 如果当前结点 root 等于 NULL，则直接返回 NULL
     （2） 如果root 等于 p 或者 q ，那这棵树一定返回 p 或者 q
     
     （3） 然后递归左右子树，因为是递归，使用函数后可认为左右子树已经算出结果，用 left 和 right 表示
     （4） 此时若 left 为空，那最终结果只要看 right；若 right 为空，那最终结果只要看 left
     （5） 如果 left 和 right 都非空，因为只给了 p 和 q 两个结点，都非空，说明一边一个，因此 root 是他们的最近公共祖先
     （6） 如果 left 和 right 都为空，则返回空（其实已经包含在前面的情况中了）
     
     */
    
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        if root == nil || root?.val == p?.val || root?.val == q?.val{
            return root
        }
        
        let left = self.lowestCommonAncestor(root?.left, p, q)
        let right = self.lowestCommonAncestor(root?.right, p, q)
        
        if left == nil {
            return right
        }
        if right == nil {
            return left
        }
        if left != nil && right != nil {
            return root
        }
        return nil
        
        //return left == nil ? right : right == nil ? left : root
        
        
    }
    
    
    var resultNode:TreeNode?
    
    func lowestCommonAncestor2(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        self.dfs(root, p, q)
        return resultNode
    }
    
    func dfs(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> Bool{
        if root == nil {
            return false
        }
        
        let lson = self.dfs(root?.left, p, q)
        let rson = self.dfs(root?.right, p, q)
        if lson && rson || ((root?.val == p?.val || root?.val == q?.val) && lson || rson) {
            resultNode = root
        }else{
            resultNode = nil
        }
        return lson && rson || ((root?.val == p?.val || root?.val == q?.val) && lson || rson)
    }
}
